package interview.algorithms.dp;

import common.Util;
import org.junit.Test;

/**
 * @author fance
 * @date 2018/5/19 9:15
 */
public class Solution {

    public long countWay(int n) {
        if (n < 1) {
            return 0;
        }
        if (n < 3) {
            return n;
        }
        long res = 0;
        long first = 2;
        long second = 1;
        for (int i = 3; i <= n; i++) {
            res = first + second;
            second = first;
            first = res;
        }
        return res;
    }

    /**
     * 生牛 f(n-1) + f(n - 3)
     * @param n
     * @return
     */
    public int cow(int n) {
        if (n < 1) {
            return 0;
        }
        if (n < 4) {
            return n;
        }
        int pre = 3;
        int preprepre = 1;
        int prepre = 2;
        int res = 0;
        for (int i = 4; i <= n; i++) {
            res = pre + preprepre;
            preprepre = prepre;
            prepre = pre;
            pre = res;
        }
        return res;
    }
    public int cowII(int n) {
        if (n < 1) {
            return 0;
        }
        if (n < 4) {
            return n;
        }
        return cowII(n - 1) + cowII(n - 3);
    }

    /**
     * 矩阵最小路径和
     * @param m
     * @return
     */
    public int minPathSum(int[][] m) {
        if (m == null || m.length < 1) {
            return 0;
        }
        int row = m.length;
        int col = m[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = m[0][0];
        for (int i = 1; i < row; i++) {
            dp[i][0] = dp[i - 1][0] + m[i][0];
        }
        for (int i = 1; i < col; i++) {
            dp[0][i] = dp[0][i - 1] + m[0][i];
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - 1]) + m[i][j];
            }
        }
        return dp[row - 1][col - 1];
    }

    public int minPathSumII(int[][] m) {
        if (m == null || m.length < 1) {
            return 0;
        }
        int more = Math.max(m.length,m[0].length);
        int less = Math.min(m.length,m[0].length);
        boolean rowMore = more == m.length;
        int[] dp = new int[less];
        dp[0] = m[0][0];
        for (int i = 1; i < less; i++) {
            dp[i] = dp[i - 1] + (rowMore ? m[0][i] : m[i][0]);
        }
        for (int i = 1; i < more; i++) {
            dp[0] = dp[0] + (rowMore ? m[i][0] : m[0][i]);
            for (int j = 1; j < less; j++) {
                dp[j] = Math.min(dp[j - 1],dp[j]) + (rowMore ? m[i][j] : m[j][i]);
            }
        }
        return dp[less - 1];
    }

    /**
     * 换钱最少货币数
     * @param arr
     * @param aim
     * @return
     */
    public int minCoinsI(int[] arr, int aim) {
        if (arr == null || arr.length < 1 || aim < 0) {
            return -1;
        }
        int n = arr.length;
        int max = Integer.MAX_VALUE;
        int[][] dp = new int[n][aim + 1];
        for (int j = 1; j <= aim; j++) {
            dp[0][j] = max;
            if (j - arr[0] >= 0 && dp[0][j - arr[0]] != max) {
                dp[0][j] = dp[0][j - arr[0]] + 1;
            }
        }
        int left = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
                left = max;
                if (j - arr[i] >= 0 && dp[i][j - arr[i]] != max) {
                    left = dp[i][j - arr[i]] + 1;
                }
                dp[i][j] = Math.min(left,dp[i - 1][j]);
            }
        }
        return dp[n - 1][aim] != max ? dp[n - 1][max] : -1;
    }

    /**
     * 只能使用一张
     * @param arr
     * @param aim
     * @return
     */
    public int minCoinsII(int[] arr, int aim) {
        if (arr == null || arr.length < 1 || aim < 0) {
            return -1;
        }
        int n = arr.length;
        int max = Integer.MAX_VALUE;
        int[][] dp = new int[n][aim + 1];
        for (int j = 1; j <= aim; j++) {
            dp[0][j] = max;
        }
        if (arr[0] <= aim) {
            dp[0][arr[0]] = 1;
        }
        int leftup = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <= aim; j++) {
                leftup = max;
                if (j - arr[i] >= 0 && dp[i - 1][j - arr[i]] != max) {
                    leftup = dp[i - 1][j - arr[i]] + 1;
                }
                dp[i][j] = Math.min(leftup,dp[i - 1][j]);
            }
        }
        return dp[n - 1][aim] != max ? dp[n - 1][aim] : -1;
    }

    /**
     * 换钱方法数 BF
     * @param arr
     * @param aim
     * @return
     */
    public int coinsI(int[] arr, int aim) {
        if (arr == null || arr.length < 1 || aim < 0) {
            return 0;
        }
        return processForCoinsI(arr,0,aim);
    }
    private int processForCoinsI(int[] arr, int index, int aim) {
        int res = 0;
        if (index == arr.length) {
            res = aim == 0 ? 1 : 0;
        } else {
            for (int i = 0; i * arr[index] <= aim; i++) {
                res += processForCoinsI(arr,index + 1, aim - arr[index] * i);
            }
        }
        return res;
    }

    /**
     * 记忆化搜索
     * @param arr
     * @param aim
     * @return
     */
    public int coinsII(int[] arr, int aim) {
        if (arr == null || arr.length < 1 || aim < 0) {
            return 0;
        }
        int[][] map = new int[arr.length + 1][aim + 1];
        return processForCoinsII(arr,0,aim,map);
    }
    private int processForCoinsII(int[] arr, int index, int aim,int[][] map) {
        int res = 0;
        if (index == arr.length) {
            res = aim == 0 ? 1 : 0;
        } else {
            int mapVal = 0;
            for (int i = 0; i * arr[index] <= aim; i++) {
                mapVal = map[index + 1][aim - arr[index] * i];
                if (mapVal != 0) {
                    res += mapVal == -1 ? 0 : mapVal;
                } else {
                    res += processForCoinsII(arr,index + 1, aim - arr[index] * i,map);
                }

            }
        }
        map[index][aim] = res == 0 ? -1 : res;
        return res;
    }

    /**
     * dp   n * aim ^2
     * @param arr
     * @param aim
     * @return
     */
    public int coinsIII(int[] arr, int aim) {
        if (arr == null || arr.length < 1 || aim < 0) {
            return 0;
        }
        int[][] dp = new int[arr.length][aim + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; arr[0] * i <= aim; i++) {
            dp[0][arr[0] * i] = 1;
        }
        int num = 0;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim ; j++) {
                num = 0;
                for (int k = 0; j - arr[i] * k >= 0; k++) {
                    num += dp[i - 1][j - arr[i] * k];
                }
                dp[i][j] = num;
            }
        }
        return dp[arr.length - 1][aim];
    }

    /**
     * n * aim
     * @param arr
     * @param aim
     * @return
     */
    public int coinsIV(int[] arr, int aim) {
        if (arr == null || arr.length < 1 || aim < 0) {
            return 0;
        }
        int[][] dp = new int[arr.length][aim + 1];
        for (int i = 0; i < arr.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; arr[0] * i <= aim; i++) {
            dp[0][arr[0] * i] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim ; j++) {
               dp[i][j] = dp[i - 1][j];
               dp[i][j] += j - arr[i] >= 0 ? dp[i][j - arr[i]] : 0;
            }
        }
        return dp[arr.length - 1][aim];
    }

    /**
     * 空间 aim
     * @param arr
     * @param aim
     * @return
     */
    public int coinsV(int[] arr, int aim) {
        if (arr == null || arr.length < 1 || aim < 0) {
            return 0;
        }
        int[] dp = new int[aim + 1];
        for (int i = 0; arr[0] * i <= aim; i++) {
            dp[arr[0] * i] = 1;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = 1; j <= aim ; j++) {
               dp[j] += j - arr[i] >= 0 ? dp[j - arr[i]] : 0;
            }
        }
        return dp[aim];
    }

    /**
     * 最长递增子序列
     * @param arr
     * @param dp
     * @return
     */
    public int[] generateLIS(int[] arr,int[] dp) {
        if (arr == null) {
            return null;
        }
        int len = 0;
        int index = 0;
        for (int i = 0; i < dp.length; i++) {
            if (dp[i] > len) {
                len = dp[i];
                index = i;
            }
        }
        int[] lis = new int[len];
        lis[--len] = arr[index];
        for (int i = index; i >= 0; i--) {
            if (arr[i] < arr[index] && dp[i] == dp[index] - 1) {
                lis[--len] = arr[i];
                index = i;
            }
        }
        return lis;
    }
    private int[] getDpForGenerateLIS(int[] arr) {
        int[] dp = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp;
    }


    /**
     * 最长公共子序列
     * @param s1
     * @param s2
     * @return
     */
    public String lcse(String s1,String s2) {
        if (s1 == null || s1.length() < 1 || s2 == null || s2.length() < 1) {
            return null;
        }
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        int[][] dp = getDpForLcse(cs1,cs2);
        int m = cs1.length - 1;
        int n = cs2.length - 1;
        char[] res = new char[dp[m][n]];
        int index = res.length - 1;
        while (index >= 0) {
            if (n > 0 && dp[m][n] == dp[m][n - 1]) {
                n--;
            } else if (m > 0 && dp[m][n] == dp[m - 1][n]) {
                m--;
            } else {
                res[index--] = cs1[m];
                m--;
                n--;
            }
        }
        return String.valueOf(res);
    }
    private int[][] getDpForLcse(char[] s1,char[] s2) {
        int[][] dp = new int[s1.length][s2.length];
        dp[0][0] = s1[0] == s2[0] ? 1 : 0;
        for (int i = 1; i < s1.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0],s1[i] == s2[0] ? 1 : 0);
        }
        for (int i = 1; i < s2.length; i++) {
            dp[0][i] = Math.max(dp[0][i - 1],s1[0] == s2[i] ? 1 : 0);
        }
        for (int i = 1; i < s1.length; i++) {
            for (int j = 1; j < s2.length; j++) {
                dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
                if (s1[i] == s2[j]) {
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - 1] + 1);
                }
            }
        }
        return dp;
    }

    public String lcst(String s1,String s2) {
        if (s1 == null || s1.length() < 1 || s2 == null || s2.length() < 1) {
            return null;
        }
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        int[][] dp = getDpForLcst(cs1,cs2);
        int end = 0;
        int max = 0;
        for (int i = 0; i < cs1.length; i++) {
            for (int j = 0; j < cs2.length; j++) {
                if (dp[i][j] > max) {
                    end = i;
                    max = dp[i][j];
                }
            }
        }
        return s1.substring(end - max + 1,end + 1);
    }


    private int[][] getDpForLcst(char[] str1,char[] str2) {
        int[][] dp = new int[str1.length][str2.length];
        for (int i = 0; i < str1.length; i++) {
            if (str1[i] == str2[0]) {
                dp[i][0] = 1;
            }
        }
        for (int i = 0; i < str2.length; i++) {
            if (str1[0] == str2[i]) {
                dp[0][i] = 1;
            }
        }

        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                if (str1[i] == str2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
            }
        }
        return dp;
    }

    /**
     * 最小编辑距离
     * @param s1
     * @param s2
     * @param ic
     * @param dc
     * @param rc
     * @return
     */
    public int minCost(String s1,String s2,int ic,int dc,int rc) {
        if (s1 == null || s1.length() < 1 || s2 == null || s2.length() < 1) {
            return 0;
        }
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        int row = cs1.length + 1;
        int col = cs2.length + 1;
        int[][] dp = new int[row][col];
        for (int i = 1; i < row; i++) {
            dp[i][0] = dc * i;
        }
        for (int i = 1; i < col; i++) {
            dp[0][i] = ic * i;
        }

        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (cs1[i - 1] == cs2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + rc;
                }

                dp[i][j] = Math.min(dp[i][j],dp[i][j - 1] + ic);
                dp[i][j] = Math.min(dp[i][j],dp[i - 1][j] + dc);
            }
        }
        return dp[row - 1][col - 1];
    }


    /**
     * 跳跃游戏
     * @param arr
     * @return
     */
    public int jump(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int jump = 0;
        int cur = 0;
        int next = 0;
        for (int i = 0; i < arr.length; i++) {
            if (cur < i) {
                jump++;
                cur = next;
            }
            next = Math.max(next,i + arr[i]);
        }
        return jump;
    }

    public int nQueue(int n) {
        if (n < 1) {
            return 0;
        }
        int[] record = new int[n];
        return nQueueCore(0,record,n);
    }
    private int nQueueCore(int i,int[] record,int n) {
        if (i == n) {
            return 1;
        }
        int res = 0;
        for (int j = 0; j < n; j++) {
            if (isValid(record,i,j)) {
                record[i] = j;
                res += nQueueCore(i + 1,record,n);
            }
        }
        return res;
    }
    private boolean isValid(int[] record,int i,int j) {
        for (int k = 0; k < i; k++) {
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 198. 打家劫舍
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0],nums[1]);
        }
        int[] dp = new int[nums.length];
        // dp 保存当前最大打劫钱数
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1],dp[0]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }

    /**
     * 746. 使用最小花费爬楼梯
     * @param cost
     * @return
     */
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i - 1],dp[i - 2]) + cost[i];
        }
        return Math.min(dp[dp.length - 1],dp[dp.length - 2]);
    }

    /**
     * 647. 回文子串
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                if (Util.isPalindrome(s.substring(i,j))) {
                    res++;
                }
            }
        }
        return res;
    }
    @Test
    public void test() {
        System.out.println(cow(8));
        System.out.println(cowII(8));
        // System.out.println(countWay(3));
       // int[] arr = {3,2,3,1,1,4};
       // System.out.println(jump(arr));
//        System.out.println(nQueue(8));
       /* int[] arr = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
        System.out.println(minCostClimbingStairs(arr));*/
    }
}
